package com.kobeliu.entity;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * leetcode 22
 *
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 *
 * 示例 1：
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：["()"]
 */
public class Demo_22_No22 {

    public static void main(String[] args) {

        System.out.println(generateParenthesis(5));


    }

//    public static List<String> generateParenthesis(int n) {
//
//    }

    /**
     * 动态规划试试
     * 击败了 5% 笑麻了
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        //dpMap
        Map<Integer,List<String>> dpMap = new HashMap<Integer, List<String>>();

        if(n==0){
            return new ArrayList<String>();
        }
        if(n==1){
            List<String> strs = new ArrayList<String>();
            strs.add("()");
            return strs;
        }
        for (int i = 1; i <= n; i++) {
            List<String> strs = new ArrayList<String>();
            if(i==1){
                strs.add("()");
                dpMap.put(i,strs);
            }else{
                String tmp = "";
                List<String> strings = dpMap.get(i - 1);
                for (String s:strings) {
                    for (int j = 0; j < s.length(); j++) {
                        tmp = s.substring(0,j)+"()"+s.substring(j);
                        if(!strs.contains(tmp)){
                            strs.add(tmp);
                        }
                    }
                }
                dpMap.put(i,strs);
            }
        }
        return dpMap.get(n);
    }
}
